package com.dragon.linkedlist;

import java.util.ConcurrentModificationException;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * 双向链表
 *
 * @author dragon
 * @version V1.0.0-RELEASE
 * @date 2019/5/19 20:32
 */
public class DoubleLinkedList<E> {

    /**
     * 链表元素个数
     */
    private int size;

    /**
     * 修改的元素的个数
     */
    private int modifyCount;

    /**
     * 头结点
     */
    private Node<E> head;

    /**
     * 尾结点
     */
    private Node<E> tail;


    private static class Node<E> {
        E item;
        Node<E> previous;
        Node<E> next;

        public Node(Node<E> previous, E item, Node<E> next) {
            this.item = item;
            this.previous = previous;
            this.next = next;
        }
    }

    /**
     * LinkedList内部实现的迭代器
     */
    private class ListItr implements ListIterator<E> {
        /**
         * 上一次返回的节点
         */
        private Node<E> lastReturned;
        /**
         * 下一个要返回的节点
         */
        private Node<E> next;
        /**
         * 一个要返回的角标
         */
        private int nextIndex;
        /**
         * 为了维持迭代器的正常的迭代,期望修改的个数
         */
        private int expectedModCount = modifyCount;

        /**
         * LinkedList 内部的 list迭代器
         *
         * @param index
         */
        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : find(index);
            nextIndex = index;
        }

        /**
         * 判断是否还有下一个元素
         *
         * @return
         */
        @Override
        public boolean hasNext() {
            return nextIndex < DoubleLinkedList.this.size;
        }

        /**
         * 返回要迭代到的元素
         *
         * @return
         */
        @Override
        public E next() {
            if (expectedModCount != modifyCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = next;
            next = next.next;
            nextIndex++;

            return lastReturned.item;
        }

        @Override
        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        @Override
        public E previous() {
            if (expectedModCount != modifyCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }
            lastReturned = next = (next == null) ? tail : next.previous;
            nextIndex--;

            return lastReturned.item;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            return nextIndex - 1;
        }

        @Override
        public void remove() {

        }

        @Override
        public void set(E e) {

        }

        @Override
        public void add(E e) {

        }
    }

    /**
     * 在 index 索引处添加 item 元素
     *
     * @param index 在角标处
     * @param item  待添加的元素
     * @return void
     * @author dragon
     * @date 2019/5/19 20:36
     * @version V1.0.0-RELEASE
     */
    public void add(int index, E item) {
        // 检查越界
        checkPositionIndex(index);
//        // 如果头结点为空,则说明是空链表,是第一次添加
//        if (head == null) {
//            head = tail = new Node<>(null, item, null);
//        } else {
//            if (index == 0) {
//                Node<E> cur = find(index);
//                head = cur.next = new Node<>(null, item, cur);
//            } else if (index == size) {
//                Node<E> cur = find(index - 1);
//                tail = cur.next = new Node(cur, item, null);
//            }else {
//                Node<E> cur = find(index);
//                Node<E> eNode = new Node<>(cur.previous, item, cur);
//                cur.previous = cur.previous.next = eNode;
//            }
//        }
        if (index == size) {
            linkLast(item);
        } else {
            linkBefore(index, item);
        }
        size++;
        modifyCount++;
    }

    /**
     * 链接最后一个元素
     *
     * @param e
     * @return void
     * @author dragon
     * @date 2019/5/20 10:02
     * @version V1.0.0-RELEASE
     */
    void linkLast(E e) {
        Node<E> cur = tail;
        Node<E> eNode = new Node<>(cur, e, null);
        tail = eNode;
        if (cur == null) {
            head = eNode;
        } else {
            cur.next = eNode;
        }
    }

    void linkBefore(int index, E e) {
        Node<E> cur = find(index);
        Node<E> eNode = new Node<>(cur.previous, e, cur);
        if (cur.previous == null) {
            head = eNode;
        } else {
            cur.previous.next = eNode;
        }
        cur.previous = eNode;
    }

    /**
     * 在首位添加元素
     *
     * @param item
     * @return void
     * @author dragon
     * @date 2019/5/20 9:11
     * @version V1.0.0-RELEASE
     */
    public void addFist(E item) {
        add(0, item);
    }

    /**
     * 在链表尾部添加元素
     *
     * @param item
     */
    public void addLast(E item) {
        add(size, item);
    }

    /**
     * 根据角标查询对应的节点
     *
     * @param index
     * @return com.dragon.linkedlist.DoubleLinkedList.Node<E>
     * @author dragon
     * @date 2019/5/20 9:05
     * @version V1.0.0-RELEASE
     */
    private Node<E> find(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("角标越界异常: index" + index);
        }
        Node<E> cur = null;
        if (index < (size >> 1)) {
            cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
        } else {
            cur = tail;
            for (int i = size - 1; i > index; i--) {
                cur = cur.previous;
            }
        }
        return cur;
    }

    /**
     * 检查角标越界问题
     *
     * @param index
     */
    private void checkPositionIndex(int index) {
        // 检查越界
        if (index < 0 || index > this.size) {
            throw new IndexOutOfBoundsException("角标越界异常,越界角标:" + index);
        }
    }

    /**
     * 删除元素
     *
     * @param e
     * @return boolean
     * @author dragon
     * @date 2019/5/20 14:20
     * @version V1.0.0-RELEASE
     */
    public boolean remove(E e) {
        if (e == null) {
            for (Node<E> cur = head; cur != null; cur = cur.next) {
                if (cur.item == null) {
                    unlink(cur);
                    return true;
                }
            }
        } else {
            for (Node<E> cur = head; cur != null; cur = cur.next) {
                if (e.equals(cur.item)) {
                    unlink(cur);
                    return true;
                }
            }
        }
        return true;
    }

    public E removeHead() {
        Node<E> f = head;
        if (f == null) {
            throw new NoSuchElementException();
        }

        return unlink(f);
    }

    public E removeTail() {
        Node<E> f = tail;
        if (f == null) {
            throw new NoSuchElementException();
        }

        return unlink(f);
    }

    /**
     * 返回listIterator 迭代器
     *
     * @param index
     * @return
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("角标越界异常;index:" + index);
        }
        return new ListItr(index);
    }

    /**
     * 链表解绑
     *
     * @param node
     * @return
     */
    E unlink(Node<E> node) {
        E element = node.item;
        Node<E> prev = node.previous;
        Node<E> next = node.next;
        // 如果是头结点, prev.next = next 就会报空指针
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            node.previous = null;
        }
        // 如果是尾结点 , next.previous = prev 也会报 空指针
        if (next == null) {
            tail = prev;
        } else {
            next.previous = prev;
            node.next = null;
        }
        node.item = null;
        size--;
        modifyCount++;

        return element;
    }

    /**
     * 重写 Object toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[head]");
        for (Node<E> cur = head; cur != null; cur = cur.next) {
            sb.append(cur.item + "==>");
        }

        return sb.toString();

    }
}
